package java_0220.leetcode;

/**
 * 二叉树找最近公共祖先
 * 分析：找公共祖先的顺便可以找出最近公共祖先
 * 是公共祖先的情况：1.左右子树有pq，公共祖先是根节点2.左和根是有pq，公共祖先是根节点3.右根，也存在公共祖先
 */
public class Num236_NearestCommomAncestor1 {
    private TreeNode nca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        lowestCommonAncestorHelper(root,p,q);
        return nca;
    }

    /**
     * 判断是否存在公共祖先，即判断以root为根节点的根节点以及左右子树中是否包含p,q
     * 用整型变量接收是否找到节点p,q
     * @param root
     * @param p
     * @param q
     * @return
     */
    private boolean lowestCommonAncestorHelper(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return false;
        }
        //判断左右子树是否存在p或q
        int left=lowestCommonAncestorHelper(root.left,p,q)?1:0;
        int right=lowestCommonAncestorHelper(root.right,p,q)?1:0;
        //判断根节点是否是p或q
        int mid=(p==root||q==root)?1:0;
        if(left+right+mid==2){
            nca=root;
        }
        return left+right+mid>0;
    }
}
